function fannkuch()
    tic
    [sum, maxflips] = run_fannkuch(9);
    toc
end

function [sum, maxflips] = run_fannkuch(n)
    p = 1:n;
    q = 1:n;
    s = 1:n;
    sign = 1;
    maxflips = 0;
    sum = 0;
    m = n - 1;

    while true
        q0 = p(1);
        if q0 ~= 1
            q(2:n) = p(2:n);
            flips = 1;
            while true
                qq = q(q0);
                if qq == 1
                    sum = sum + sign * flips;
                    if flips > maxflips
                        maxflips = flips;
                    end
                    break;
                end
                q(q0) = q0;
                if q0 >= 4
                    i = 2;
                    j = q0 - 1;
                    while i < j
                        t = q(i);
                        q(i) = q(j);
                        q(j) = t;
                        i = i + 1;
                        j = j - 1;
                    end
                end
                q0 = qq;
                flips = flips + 1;
            end
        end

        if sign == 1
            t = p(2);
            p(2) = p(1);
            p(1) = t;
            sign = -1;
        else
            t = p(2);
            p(2) = p(3);
            p(3) = t;
            sign = 1;
            for i = 3:n
                sx = s(i);
                if sx ~= 1
                    s(i) = sx - 1;
                    break;
                end
                if i == m
                    return;
                end
                s(i) = i;
                t = p(1);
                p(1:i) = p(2:i+1);
                p(i + 1) = t;
            end
        end
    end
end
